package chapter01;

public class StrStr {
    public int strStr(String haystack, String needle) {
        if(needle==null){
            return 0;
        }
        if(haystack.length()<needle.length()||needle.length()<1){
            return -1;
        }
        char[] str1=haystack.toCharArray();
        char[] str2=needle.toCharArray();
        int[] next=getArrayNext(str2);
        int i1=0;
        int i2=0;
        while (i1<str1.length&&i2<str2.length){
            if(str1[i1]==str2[i2]){
                i1++;
                i2++;
            }else if(i2==0){
                i1++;
            }else{
                i2=next[i2];
            }
        }

        return i2==str2.length?i1-i2:-1;
    }

    public int[] getArrayNext(char[] str){
        if(str.length==1){
            return new int[]{-1};
        }
        int[] next=new int[str.length];
        next[0]=-1;
        next[1]=0;
        int i=2;
        int cn=0;
        while (i<next.length){
            if(str[i-1]==str[cn]){
                next[i++]=++cn;
            }else if(cn>0){
                cn=next[cn];
            }else{
                next[i++]=0;
            }
        }
        return next;
    }


}
